import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/16 15:59
 * @description 两个区间S1[l1, r1], S2[l2, r2]， 若没有交集，那么 r1 < l2 或者 l1 > r2, 如果两者均不满足，那么S1 与 S2必有交集，
 * 交集为 [max(l1, l2), min(r1, r2)], 并集 [min(l1, l2), max(r1, r2)]
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] intervals = {{1,3}, {6,9}};
        int[] newInterval = {2,5};
        solution.insert(intervals, newInterval);
    }
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int left = newInterval[0], right = newInterval[1];
        boolean placed = false;
        List<int[]> ans = new ArrayList<>();
        for (int[] in : intervals) {
            if (in[0] > right) {
                // 在插入区间右侧，且无交集
                if(!placed) {
                    ans.add(new int[]{left, right});
                    placed = true;
                }
                ans.add(in);
            }else if (in[1] < left) {
                // 在插入区间的左边 且无交集
                ans.add(in);
            }else {
                // 存在交集，合并两个区间
                right = Math.max(in[1], right);
                left = Math.min(in[0], left);
            }
        }
        if (!placed) {
            ans.add(new int[]{left, right});
        }
        return ans.toArray(new int[][]{});
    }
}
